/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2003-2019. All rights reserved.
 ******************************************************************************************/

#pragma once

/******************************************************************************************
 * 沿关键码k对应的查找链，找到首个可用空桶（仅供插入词条时调用）
 * 试探策略多种多样，可灵活选取；这里仅以线性试探策略为例
 ******************************************************************************************/
template <typename K, typename V> int Hashtable<K, V>::probe4Free ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   //*DSA*/printf(" ->%d", r); //首个试探的桶单元地址
   while ( ht[r] ) r = ( r + 1 ) % M; //沿查找链逐桶试探，直到首个空桶（无论是否带有懒惰删除标记）
//*DSA*/   while (ht[r]) { r = (r+1) % M; printf(" ->%d", r); } printf("\n");
   return r; //为保证空桶总能找到，装填因子及散列表长需要合理设置
}
